/**
 * @file 011.0和1个数相同的子数组.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-12-08
 *
 * @copyright Copyright (c) 2021
 *
 */

#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

template <typename T>
void print(const T &t)
{
    typename T::const_iterator it = t.begin();
    for (; it != t.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    int findMaxLength(vector<int> &nums)
    {
        // 利用前缀和的特点：前缀和之差=区间和
        // 把0看成-1，问题转变成：和为0的最长子数组
        int n = nums.size();
        unordered_map<int, int> mp; // {和：索引}
        mp[0] = -1;                 // 空前缀和为0，因此记为-1
        int preSum = 0;
        int maxLen = 0;
        for (int i = 0; i < n; ++i) {
            preSum += nums[i] == 0 ? -1 : 1;
            if (mp.find(preSum) != mp.end()) {        // mp[preSum - k] (k==0)
                maxLen = max(maxLen, i - mp[preSum]); // 当前前缀和索引-上一个前缀和索引=区间长度
            } else {
                mp[preSum] = i;
            }
        }
        return maxLen;
    }
};

int main()
{
    vector<int> nums1 = {0, 0, 1, 0, 0, 0, 1, 1};
    vector<int> nums2 = {0, 1, 1};
    cout << Solution().findMaxLength(nums1) << endl;
    cout << Solution().findMaxLength(nums2) << endl;
    return 0;
}